package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - 按摩师
        Solution solution1 = new Solution();
        System.out.println("按摩师:");
        int[] nums1 = {1, 2, 3, 1};
        System.out.println("nums=[1,2,3,1]: " + solution1.massage(nums1)); // 4
        int[] nums2 = {2, 7, 9, 3, 1};
        System.out.println("nums=[2,7,9,3,1]: " + solution1.massage(nums2)); // 12

        // 测试用例 - 打家劫舍II
        Solution2 solution2 = new Solution2();
        System.out.println("\n打家劫舍II:");
        int[] nums3 = {2, 3, 2};
        System.out.println("nums=[2,3,2]: " + solution2.rob(nums3)); // 3
        int[] nums4 = {1, 2, 3, 1};
        System.out.println("nums=[1,2,3,1]: " + solution2.rob(nums4)); // 4
        int[] nums5 = {1, 2, 3};
        System.out.println("nums=[1,2,3]: " + solution2.rob(nums5)); // 3
    }

    // 按摩师
    static class Solution {
        int[] f;  // f[i]: 选择第i个预约的最大时长
        int[] g;  // g[i]: 不选第i个预约的最大时长

        public int massage(int[] nums) {
            int m = nums.length;
            if (m == 0) return 0;

            f = new int[m];
            g = new int[m];

            // 初始化
            f[0] = nums[0];
            g[0] = 0;

            // 状态转移
            for (int i = 1; i < m; i++) {
                f[i] = g[i - 1] + nums[i];  // 选第i个，加上前一个不选的最优值
                g[i] = Math.max(f[i - 1], g[i - 1]);  // 不选第i个，取前一个的最优值
            }

            return Math.max(f[m - 1], g[m - 1]);
        }
    }

    // 打家劫舍II
    static class Solution2 {
        int n;

        public int rob(int[] nums) {
            n = nums.length;
            if (n == 0) return 0;
            else if (n == 1) return nums[0];
            else if (n == 2) return Math.max(nums[0], nums[1]);

            // 情况1：考虑第一间，不考虑最后一间，范围 [0, n-2]
            // 情况2：不考虑第一间，考虑最后一间，范围 [1, n-1]
            return Math.max(rob1(nums, 0, n - 2), rob1(nums, 1, n - 1));
        }

        // 线性打家劫舍（处理 [left, right] 范围）
        public int rob1(int[] nums, int left, int right) {
            int[] f = new int[n];  // 偷第 i 间房的最大金额
            int[] g = new int[n];  // 不偷第 i 间房的最大金额

            // 初始化起点
            f[left] = nums[left];
            g[left] = 0;

            // 从 left+1 遍历到 right
            for (int i = left + 1; i <= right; i++) {
                f[i] = g[i - 1] + nums[i];      // 偷i = 不偷i-1的最优 + nums[i]
                g[i] = Math.max(f[i - 1], g[i - 1]);  // 不偷i = 前面的最优
            }

            // 返回最后位置偷或不偷的最大值
            return Math.max(f[right], g[right]);
        }
    }
}